package bintree.heap;

import java.util.ArrayList;

/**
 * 基于int的大根堆实现
 * 元素从索引0开始存储
 * parent (i) = (i - 1) / 2;
 * left (i) = 2i + 1;
 * right (i) = 2i + 2;
 * @author yuisama
 * @date 2021/12/10 15:40
 **/
public class MaxHeap {
    private ArrayList<Integer> elementData;

    /**
     * 在当前堆中添加一个新元素(在数组末尾添加，然后进行siftUp)
     * @param val
     */
    public void add(int val) {
        // 在当前数组最后添加元素，保证仍然为完全二叉树
        elementData.add(val);
        // 调整当前树，使其满足堆的性质
        siftUp(getSize() - 1);
    }

    /**
     * 取出最大值
     * 1.最大值即为根节点
     * 2.将最后一个元素顶到根节点然后移除最后一个位置元素
     * 3.进行siftDown操作
     * @return
     */
    public int extractMax() {
        int max = peek();
        // 将最后一个元素顶到堆顶
        elementData.set(0,elementData.get(getSize() - 1));
        elementData.remove(getSize() - 1);
        siftDown(0);
        return max;
    }

    /**
     * 向下调整当前位置元素，使其具备堆的性质
     * @param i 要调整的元素索引
     */
    private void siftDown(int i) {
        // 终止条件，左孩子不越界，即还没判断到叶子结点
        while (leftChild(i) < getSize()) {
            int j = leftChild(i);
            // 右孩子存在且值大于左孩子
            if (j + 1 < getSize() && elementData.get(j) < elementData.get(j + 1)) {
                j = j + 1;
            }
            // 此时element[j]存储了左右孩子的最大值
            if (elementData.get(i) < elementData.get(j)) {
                // 当前结点小于孩子结点，交换
                swap(i,j);
                i = j;
            }else {
                // 此时结点已经大于左右孩子，满足堆
                break;
            }
        }
    }

    private int peek() {
        if (isEmpty()) {
            System.err.println("heap is empty!");
            return -1;
        }
        return elementData.get(0);
    }

    /**
     * 元素上浮操作
     * @param k 要上浮的元素索引
     */
    private void siftUp(int k) {
        // 循环终止条件: k == 0(已经为根节点) || 当前结点值已经 <= data[parent]
        while (k > 0 && elementData.get(k) > elementData.get(getParent(k))) {
            // 交换当前结点和父节点
            swap(k,getParent(k));
            // 继续判断交换后的结点和其父节点大小关系
            k = getParent(k);
        }
    }

    private void swap(int k, int parent) {
        int tmp = elementData.get(k);
        elementData.set(k,elementData.get(parent));
        elementData.set(parent,tmp);
    }

    public MaxHeap() {
        elementData = new ArrayList<>();
    }

    public MaxHeap(int capacity) {
        elementData = new ArrayList<>(capacity);
    }

    /**
     * replace操作，将堆顶元素替换为newValue，返回堆顶元素
     * @param newVal
     * @return
     */
    public int replace(int newVal) {
        int oldVal = peek();
        elementData.set(0,newVal);
        siftDown(0);
        return oldVal;
    }

    /**
     * 将传入的数组arr堆化
     * heapify操作
     * @param arr
     */
    public MaxHeap(int[] arr) {
        this.elementData = new ArrayList<>(arr.length);
        for (int j : arr) {
            elementData.add(j);
        }
        if (elementData.size() != 1) {
            // 从最后一个非叶子结点开始siftDown
            for (int i = getParent(getSize() - 1); i >= 0; i--) {
                siftDown(i);
            }
        }
    }

    public int getSize() {
        return elementData.size();
    }

    public boolean isEmpty() {
        return getSize() == 0;
    }

    private int getParent(int i) {
        return (i - 1) / 2;
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("top [");
        for (int i = 0; i < getSize(); i++) {
            sb.append(elementData.get(i));
            if (i != getSize() - 1) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
